/**
 *  求二叉树直径
 */
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr){};
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){};
    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x), left(left), right(right){};
    void setVal(int x) { val = x; }
    void setAttribute(int x, TreeNode* l, TreeNode* r) {
        val = x;
        left = l;
        right = r;
    }
    void setChildren(TreeNode* l, TreeNode* r) {
        left = l;
        right = r;
    }
};

class Solution {
public:
    int total = 1;
    /**
     * 获取树的最大
     */
    int getMaxDiameter(TreeNode* tree) {
        getDepth(tree);
        return total + 1;
    }

    int getDepth(TreeNode* tree) {
        if (tree == nullptr) {
            return 0;
        }

        // 获取左子树高度
        int left_children_height = getDepth(tree->left);
        // 获取右子树高度
        int right_children_height = getDepth(tree->right);
        total = max((left_children_height + right_children_height), total);
        return max(left_children_height, right_children_height) + 1;
    }
};

void test() {
    // 1. 构造一棵树。
    TreeNode* t1 = new TreeNode(1);
    TreeNode* t2 = new TreeNode(2);
    TreeNode* t3 = new TreeNode(3);
    TreeNode* t4 = new TreeNode(4);
    TreeNode* t5 = new TreeNode(5);
    TreeNode* t6 = new TreeNode(6);

    t1->setChildren(t2, t3);
    t2->setChildren(t4, t5);
    t5->setChildren(t6, nullptr);

    Solution s;
    cout << "二叉树的直径为: " << s.getMaxDiameter(t1) << endl;
}

int main() {
    test();
    return 0;
}